﻿#define _CRT_SECURE_NO_WARNINGS 1

//题目:
//将给定的单链表\ L L： L_0→L_1→…→L_{ n - 1 }→L_ nL​
//重新排序为：L_0→L_n →L_1→L_{ n - 1 }→L_2→L_{ n - 2 }→…L​
//要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
//数据范围：链表长度 0≤n≤20000 ，链表中每个节点的值满足  10000≤val≤1000
//要求：空间复杂度 O(n)O(n) 并在链表上进行操作而不新建链表，时间复杂度 O(n)O(n)
//进阶：空间复杂度 O(1)O(1) ， 时间复杂度 O(n)O(n)

#include<stdio.h>
typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode;

void reorderList(struct ListNode* head)
{
    // write code here
    if (head && head->next && head->next->next)//为空,或者仅有一个或两个结点时不做处理
    {
        struct ListNode* tailprev = head;
        struct ListNode* headtmp = head;

        //数出有几个结点
        int count = 0;
        struct ListNode* counttmp = head;
        while (counttmp)
        {
            count++;
            counttmp = counttmp->next;
        }

        while (headtmp->next && headtmp->next != tailprev)
        {
            tailprev = headtmp;
            //找尾巴
            while (tailprev->next->next)
                tailprev = tailprev->next;

            if (headtmp->next && headtmp->next != tailprev && count % 2 == 0)//此时最后还剩两个结点
            {
                struct ListNode* tail = tailprev->next;
                tail->next = headtmp->next;
                headtmp->next = tail;
                tailprev->next = NULL;

                headtmp = headtmp->next->next;
            }
            if (headtmp->next && count % 2 == 1)//此时最后还剩三个结点
            {
                struct ListNode* tail = tailprev->next;
                tail->next = headtmp->next;
                headtmp->next = tail;
                tailprev->next = NULL;

                headtmp = headtmp->next->next;
            }
        }
    }
}

int main()
{

    return 0;
}